{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Best Sightseeing Pair"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxScoreSightseeingPair"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最佳观光组合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数数组 <code>values</code>，其中 <code>values[i]</code> 表示第 <code>i</code> 个观光景点的评分，并且两个景点 <code>i</code> 和 <code>j</code> 之间的 <strong>距离</strong> 为 <code>j - i</code>。</p>\n",
    "\n",
    "<p>一对景点（<code>i < j</code>）组成的观光组合的得分为 <code>values[i] + values[j] + i - j</code> ，也就是景点的评分之和<strong> 减去 </strong>它们两者之间的距离。</p>\n",
    "\n",
    "<p>返回一对观光景点能取得的最高分。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>values = [8,1,5,2,6]\n",
    "<strong>输出：</strong>11\n",
    "<strong>解释：</strong>i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>values = [1,2]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 <= values.length <= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 <= values[i] <= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [best-sightseeing-pair](https://leetcode.cn/problems/best-sightseeing-pair/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [best-sightseeing-pair](https://leetcode.cn/problems/best-sightseeing-pair/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[8,1,5,2,6]', '[1,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values) -> int:\n",
    "        start_value = values[0]\n",
    "        location = 0\n",
    "        max_value = start_value + location\n",
    "        for i in range(1, len(values)):\n",
    "            temp_value = start_value + location + values[i] - i\n",
    "            if temp_value > max_value:\n",
    "                max_value = temp_value\n",
    "            if start_value + location < values[i] + i:\n",
    "                start_value = values[i]\n",
    "                location = i\n",
    "\n",
    "        return max_value\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        N = len(values)\n",
    "        p = values[0]\n",
    "        ans = 0\n",
    "        for i in range(1, N):\n",
    "            ans = max(ans, p+values[i]-i)\n",
    "            p = max(p, values[i]+i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        pre = values[0]\n",
    "        res = -10000\n",
    "        for i in range(1, len(values)):\n",
    "            res = max(res, values[i] + pre - 1)\n",
    "            pre = max(pre - 1, values[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        pre_max = values[0]\n",
    "        res = 0\n",
    "        for index in range(1, len(values)):\n",
    "            value = values[index]\n",
    "            res = max(res, value - index + pre_max)\n",
    "            if pre_max <= value+index:\n",
    "                pre_max = value+index\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "\n",
    "        max_v = 0\n",
    "        mx = values[0]\n",
    "        for j in range(1, n):\n",
    "            max_v = max(max_v, mx + values[j] - j)\n",
    "\n",
    "            mx = max(mx, values[j] + j)\n",
    "        \n",
    "        return max_v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        maxValue = 0\n",
    "        preMax = values[0]\n",
    "        for i in range(1, len(values)):\n",
    "            val = preMax + values[i] - i\n",
    "            maxValue = max(maxValue, val)\n",
    "            preMax = max(values[i] + i, preMax)\n",
    "        return maxValue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "      ans, dp = 0, values[0]\n",
    "      for i in range(1, len(values)):\n",
    "        dp -= 1\n",
    "        ans, dp = max(ans, dp + values[i]), max(dp, values[i])\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''给你一个正整数数组 values,其中values[i] 表示第i个观光景点的评分，并且两个景点 i和j之间的距离为j-i。\n",
    "一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，\n",
    "也就是景点的评分之和减去它们两者之间的距离。返回一对观光景点能取得的最高分。'''\n",
    "'''需要注意的是，一对景点之间的距离是个迷惑项，(values[i]+i)+(values[j]-j)才是正确的思路，\n",
    "通过一次遍历，我们可以预先取得下标为[0,j)和j的结点的分数,进而我们可以以O(N)的时间复杂度完成算法设计'''\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\tdef maxScoreSightseeingPair(self, values: list[int]) -> int:\n",
    "\t\tmaxScored = values[0] + 0\n",
    "\t\tans = 0\n",
    "\t\tfor j in range(1, len(values)):\n",
    "\t\t\tans = max(ans, maxScored + values[j] - j)\n",
    "\t\t\tmaxScored = max(maxScored, values[j] + j)\n",
    "\t\treturn ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values) -> int:\n",
    "        # values[i] + values[j] + i - j = \n",
    "        # (values[i] + i) + (values[j] - j)\n",
    "        \n",
    "        max_value_i_plus_i = 0\n",
    "        max_score = 0\n",
    "        \n",
    "        for j, value in enumerate(values): \n",
    "            max_score = max(max_score, max_value_i_plus_i + value - j)\n",
    "            max_value_i_plus_i = max(max_value_i_plus_i, value + j)\n",
    "            \n",
    "        return max_score\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        res = -1\n",
    "        m1 = values[0] + 0\n",
    "        for i in range(1, len(values)):\n",
    "            res = max(res, m1 + values[i] - i)\n",
    "            m1 = max(m1, values[i] + i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        last = values[0]\n",
    "        ans = -inf\n",
    "        n = len(values)\n",
    "        for i in range(1,n):\n",
    "            ans = max(ans,values[i]-i+last)\n",
    "            last = max(last,values[i]+i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        res = 0\n",
    "        pre_max = values[0] + 0\n",
    "        for j in range(1, len(values)):\n",
    "            res = max(res, pre_max + values[j] - j)\n",
    "            pre_max = max(pre_max, values[j] + j)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        pre_max = values[0]\n",
    "        res = 0\n",
    "        for index in range(1, len(values)):\n",
    "            value = values[index]\n",
    "            res = max(res, value - index + pre_max)\n",
    "            if pre_max <= value+index:\n",
    "                pre_max = value+index\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        a, b = 0, 1\n",
    "        c = values[a] + values[b] - (b - a) # 初始化答案\n",
    "        while b < n:\n",
    "            s = values[a] + values[b] - (b - a) # 计算当前观光组合得分s\n",
    "            c = max(c, s)\n",
    "            if values[a] + a < values[b] + b: # 移动指针的条件判断\n",
    "                a = b\n",
    "                b += 1\n",
    "            else:\n",
    "                b += 1\n",
    "        return c\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        a = values[0]-1\n",
    "        m = values[1]+a\n",
    "\n",
    "        for i in range(2,len(values)):\n",
    "            a = max(a - 1, values[i-1]-1)\n",
    "            m = max(values[i]+a,m)\n",
    "\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        dp = [0 for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            dp[i] = max((dp[i - 1] + values[i] - values[i - 1] - 1), values[i] + values[i - 1] - 1)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        ans, max_val = values[0], values[0]\n",
    "        for j in range(1, n):\n",
    "            ans = max(ans, max_val + values[j] - j)\n",
    "            max_val = max(max_val, values[j] + j)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        left=0\n",
    "        max_=float('-inf')\n",
    "        for i in range(1,len(values)):\n",
    "            max_=max(max_,values[left]+values[i]+left-i)\n",
    "            if values[i]+i>values[left]+left:\n",
    "                left=i\n",
    "        return max_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        left=values[0]\n",
    "        res=-1\n",
    "        for i in range(1,len(values)):\n",
    "            res=max(res,left+values[i]-i)\n",
    "            left=max(left,values[i]+i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        # (A[i] + i) + (A[j] - j)\n",
    "        if len(values) < 2:\n",
    "            return 0\n",
    "        ans = float('-inf')\n",
    "        mx = 0\n",
    "        for i in range(len(values)):\n",
    "            ans = max(ans, mx + values[i] - i)\n",
    "            mx = max(mx, values[i] + i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n=len(values)\n",
    "        output=float(\"-inf\")\n",
    "        pre_max=values[0]+0\n",
    "        for j in range(1,n):\n",
    "            output=max(output,pre_max+values[j]-j)\n",
    "            pre_max=max(pre_max,values[j]+j)\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        max_i = values[0] + 0  # 初始化最大的 values[i] + i 值\n",
    "        max_score = 0  # 初始化最高得分\n",
    "        for j in range(1, len(values)):\n",
    "            # 计算可能的最高得分\n",
    "            max_score = max(max_score, max_i + values[j] - j)\n",
    "            # 更新最大的 values[i] + i 值\n",
    "            max_i = max(max_i, values[j] + j)\n",
    "        return max_score\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        ans,mx=0,values[0]\n",
    "        for j in range(1,len(values)):\n",
    "            ans=max(ans,mx+values[j]-j)\n",
    "            mx=max(mx,values[j]+j)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        mx = values[0]\n",
    "        ans = 0\n",
    "        for j in range(1, n):\n",
    "            ans = max(ans, values[j] - j + mx)\n",
    "            mx = max(mx, values[j] + j)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        ans, premax = 0, values[0]\n",
    "        for i in range(1, len(values)):\n",
    "            ans = max(ans, premax + values[i] - i)\n",
    "            premax = max(premax, values[i] + i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 遍历\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        ans = 0\n",
    "        mx = values[0] + 0\n",
    "        \n",
    "        for j in range(1, len(values)):\n",
    "            ans = max(ans, mx + values[j] - j)\n",
    "            # 边遍历边维护\n",
    "            mx = max(mx, values[j] + j)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        max_score = 0\n",
    "        max_i = values[0]\n",
    "        for j in range(1, len(values)):\n",
    "            max_score = max(max_score, max_i + values[j] - j)\n",
    "            max_i = max(max_i, values[j] + j)\n",
    "        return max_score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        res = 0\n",
    "        tmp = values[0]\n",
    "\n",
    "        for i in range(1,len(values)):\n",
    "            res = max(res,tmp+values[i]-i)\n",
    "            tmp = max(tmp,values[i]+i)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        buff = values[0] # 初始buff\n",
    "        ans = 0\n",
    "        for j in range(1, len(values)):\n",
    "        # 随着时间推移，buff的效力不断减少\n",
    "        # 初始效力为某个A[i], i < j\n",
    "        # 随时间减少的效力正好为 j - i\n",
    "        # 因此当前buff的剩余效力恰为 A[i] + i - j\n",
    "            buff -= 1\n",
    "            # 根据当前buff默默算一下自己的战斗力（战5渣..)\n",
    "            ans = max(ans, values[j] + buff)\n",
    "            # 看看当前buff剩余效力有没有刷新buff好，没有则刷新buff\n",
    "            buff = max(buff, values[j])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        ans = 0\n",
    "        pre = -inf\n",
    "        for x in values:\n",
    "            ans = max(ans, pre + x)\n",
    "            pre = max(pre, x)\n",
    "            pre -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        import sortedcontainers\n",
    "        res, l = 0, sortedcontainers.SortedList()\n",
    "        for i in range(len(values)): l.add(values[i]-i)\n",
    "        for i in range(len(values)-1):\n",
    "            l.discard(values[i]-i)\n",
    "            res = max(res, values[i]+i+l[-1])\n",
    "        return res\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        stack = []\n",
    "        ans = -inf\n",
    "        heappush(stack,-values[0])\n",
    "        n = len(values)\n",
    "        for i in range(1,n):\n",
    "            ans = max(ans,values[i]-i-stack[0])\n",
    "            heappush(stack,-values[i]-i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        res = 0\n",
    "        mx = values[0]\n",
    "        for i in range(1,len(values)):\n",
    "            res = max(res,mx+values[i]-i)\n",
    "            mx = max(mx,values[i]+i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        mx = values[0]\n",
    "        ans = [0] * n\n",
    "        for j in range(1, n):\n",
    "            ans[j] = values[j] - j + mx\n",
    "            mx = max(mx, values[j] + j)\n",
    "        return max(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        max_value = values[0] + values[1] - 1\n",
    "        pre_max = max(values[0]-1, values[1])\n",
    "        for i in range(2, len(values)):\n",
    "            pre_max-=1\n",
    "            max_value = max(max_value, pre_max+values[i])\n",
    "            pre_max = max(pre_max, values[i])\n",
    "        return max_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        for i in range(len(values)):\n",
    "            values[i]=values[i]-i\n",
    "        res=0\n",
    "        mx=values[0]\n",
    "        for i in range(1,len(values)):\n",
    "            res=max(res,mx+values[i])\n",
    "            mx=max(mx,values[i]+2*i)\n",
    "        return res    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        for i in range(len(values)):\n",
    "            values[i]=values[i]-i\n",
    "        res=0\n",
    "        mx=values[0]\n",
    "        for i in range(1,len(values)):\n",
    "            res=max(res,mx+values[i])\n",
    "            mx=max(mx,values[i]+2*i)\n",
    "        return res    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        imax = values[0]\n",
    "        res = imax + values[1] - 1\n",
    "        for j in range(2, len(values)):\n",
    "            if (s := values[j-1] + j - 1) > imax:\n",
    "                imax = s\n",
    "            if (s := imax + values[j] - j) > res:\n",
    "                res = s\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\r\n",
    "        ans = 0\r\n",
    "        mx = values[0] + 0\r\n",
    "        for j in range(1, len(values)):\r\n",
    "            ans = max(ans, mx + values[j] - j)\r\n",
    "            mx = max(mx, values[j] + j)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        max_pre = values[0]\n",
    "        res = 0\n",
    "        for i in range(1, n):\n",
    "            res = max(res, values[i] - i + max_pre)\n",
    "            max_pre = max(max_pre, values[i] + i)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        res = values[0] + values[1] - 1\n",
    "        dp = res\n",
    "        for i in range(2, n):\n",
    "            dp = max(dp + values[i] - values[i-1] - 1, values[i] + values[i-1] -1)\n",
    "            res = max(res, dp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        ans=0\n",
    "        maxValue=0\n",
    "        for i in range(len(values)):\n",
    "            ans=max(ans,maxValue+values[i]-i)\n",
    "            maxValue=max(maxValue,values[i]+i)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        mx=values[0]\n",
    "        ans=0\n",
    "        for j in range(1,len(values)):\n",
    "            cur=values[j]-j\n",
    "            ans=max(ans,mx+cur)\n",
    "            mx=max(mx,values[j]+j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, A: List[int]) -> int:\n",
    "        buff=A[0]\n",
    "        ans=0\n",
    "        for j in range(1,len(A)):\n",
    "            buff-=1\n",
    "            ans=max(ans,buff+A[j])\n",
    "            buff=max(buff,A[j])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        ans = 0\n",
    "        a = values[0]\n",
    "        for i in range(1,len(values)):\n",
    "            a -= 1\n",
    "            ans = max(ans,values[i] + a)\n",
    "            a = max(a,values[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        # k = values[i]+i + (values[j]-j)\n",
    "        n = len(values)\n",
    "        ans,mx = 0,values[0]+0\n",
    "        for j in range(1,n):\n",
    "            ans = max(ans,mx+values[j]-j)\n",
    "            mx = max(mx,values[j]+j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        a=values[0]+values[1]-1\n",
    "        b=max(values[0],values[1]+1)\n",
    "        for i in range(2,len(values)):\n",
    "            if (s:=b+values[i]-i)>a:\n",
    "                a=s\n",
    "            if (s:=values[i]+i)>b:\n",
    "                b=s\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        # j=1,初始化res[1],imax[1]\n",
    "        # score = V[i]+V[j]+i-j\n",
    "        res=values[0]+values[1]+0-1\n",
    "        imax=max(values[0]+0,values[1]+1)\n",
    "        for j in range(2,len(values)):\n",
    "            # walrus operator\n",
    "            if (tmp:=values[j-1]+j-1)>imax:\n",
    "                imax=tmp\n",
    "            if (tmp:=imax+values[j]-j)>res:\n",
    "                res=tmp\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        mtv = values[0]\n",
    "        mti = 0\n",
    "        ans = 0\n",
    "        for i in range(1,len(values)):\n",
    "            ans = max(mtv + values[i] - i + mti, ans)\n",
    "            if values[i] > mtv - i + mti:\n",
    "                mtv = values[i]\n",
    "                mti = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        ans = 0\n",
    "        mx = values[0] + 0\n",
    "        \n",
    "        for j in range(1, len(values)):\n",
    "            ans = max(ans, mx + values[j] - j)\n",
    "            # 边遍历边维护\n",
    "            mx = max(mx, values[j] + j)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        res = 0\n",
    "        premax = values[0] + 0\n",
    "        for j in range(1, len(values)):\n",
    "            res = max(res, values[j] - j + premax)\n",
    "            premax = max(premax, values[j] + j)\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        '''\n",
    "        n = len(values)\n",
    "        ans = 0\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                if values[i] + values[j] + i - j > ans:\n",
    "                    ans = values[i] + values[j] + i - j\n",
    "        return ans\n",
    "        '''\n",
    "        n = len(values)\n",
    "        ans = 0\n",
    "        maxSightseeingIndex = values[0] + 0\n",
    "        for i in range(1,n):\n",
    "            ans = max(ans,maxSightseeingIndex + values[i] - i)\n",
    "            maxSightseeingIndex = max(values[i] + i,maxSightseeingIndex)\n",
    "            #print(ans, maxSightseeingIndex)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        dp = values[0]\n",
    "        ans = 0\n",
    "        for i in range(1,len(values)):\n",
    "            dp -= 1\n",
    "            ans = max(dp + values[i], ans)\n",
    "            if values[i] > dp:\n",
    "                dp = values[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        if len(values) < 2:\n",
    "            return -1\n",
    "        left = values[0]\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(1, len(values), 1):\n",
    "            ans = max(ans, left + values[i] - i)\n",
    "            left = max(left, values[i] + i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        res = 0\n",
    "        pre_imax = 0\n",
    "        for j in range(1, len(values)):\n",
    "            pre_imax = max(pre_imax, (values[j-1]+j-1))\n",
    "            res = max(res, pre_imax+values[j]-j)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        max_i = 0\n",
    "        n = len(values)\n",
    "        ans = 0\n",
    "        for j in range(n):\n",
    "            ans = max(ans,values[j]-j+max_i)\n",
    "            max_i = max(max_i,values[j]+j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "\n",
    "        n = len(values)\n",
    "        candidate = values[-1] #= []\n",
    "        res = 0\n",
    "        for i in range(n-2, -1, -1):\n",
    "            # 先遍历candidates 他是后面可能更高的组合,\n",
    "            # candidates 不用记住值，遍历后直接减1就行了，\n",
    "            # 当前元素加入candidates后 所有小于x的人都不用看了 其实是单调栈吧\n",
    "            # x ... 56 这56是一个地位\n",
    "            \n",
    "            # for j, c in enumerate(candidates):\n",
    "            #     res = max(res, values[i] + candidates[j])\n",
    "            #     candidates[j] -= 1\n",
    "            #     if candidates[i] == 0\n",
    "            candidate -= 1\n",
    "            res = max(res, values[i] + candidate)\n",
    "            candidate = max(candidate, values[i])\n",
    "        return res\n",
    "\n",
    "\n",
    "            # 再过滤candidates"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "        values[i] + values[j] + i - j\n",
    "        (values[i] + i) + values[j] - j\n",
    "        维护values[i] + i最大值，枚举答案 max(left + right)\n",
    "    '''\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        ans = left = 0\n",
    "        for i, x in enumerate(values):\n",
    "            ans = max(ans, left + x - i)\n",
    "            left = max(left, x + i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        res = 0\n",
    "        left = values[0]\n",
    "        for i in range(1,len(values)):\n",
    "            res = max(res,values[i] - i + left)\n",
    "            left = max(left,values[i] + i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        mx = [0]*n\n",
    "        mx[0] = values[0]\n",
    "        ans = [0] * n\n",
    "        for j in range(1, n):\n",
    "            mx[j] = max(mx[j-1], values[j] + j)\n",
    "            ans[j] = values[j] - j + mx[j-1]\n",
    "        return max(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        zu = [0]*len(values)\n",
    "        for i in range(len(values)):\n",
    "            zu[i] = values[i]-i \n",
    "        max_index = [0]*len(values)\n",
    "        max_index[-1] = len(values) - 1 \n",
    "        for i in range(len(values)-2,-1,-1):\n",
    "            if zu[i] > zu[max_index[i+1]]:\n",
    "                max_index[i] = i \n",
    "            else:\n",
    "                max_index[i] = max_index[i+1]\n",
    "        res = -inf\n",
    "        for i in range(len(values)-1):\n",
    "            res = max(res,i - max_index[i+1] + values[i] + values[max_index[i+1]])\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
